我們從最小值的理論存在性，轉向優化問題的演算法核心。我們的核心目標是 最小化 $f(x)$ (9.1) 其中 $f: \mathbf{R}^n \to \mathbf{R}$ 是凸函數且二階連續可微。由於 $f$ 可微且凸，點 $x^*$ 為最優解的充要條件是 $\nabla f(x^*) = 0$。
演算法框架
數值方法構建一個 最小化序列：一組點列 $x^{(0)}, x^{(1)}, \dots \in \text{dom } f$，使得當 $k \to \infty$ 時，$f(x^{(k)}) \to p^*$。每一步透過 $x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}$ 更新位置，其中 $\Delta x$ 為下降方向。
初始化與收斂性
本章所描述的方法需要一個合適的起始點 $x^{(0)}$。起始點必須位於 $\text{dom } f$ 中，且子水準集 $S = \{x \in \text{dom } f \mid f(x) \le f(x^{(0)})\}$ 必須是閉集。這確保了序列能維持在一個行為良好的區域內，此時海森矩陣能提供有用的資訊。
下降方向
最簡單的方向是 $\Delta x = -\nabla f(x)$。然而，效率通常需要透過 最陡下降方向：
- 二次範數： $\|z\|_P = (z^T P z)^{1/2} = \|P^{1/2}z\|_2$。
- $L_\infty$ 範數： $\Delta x_{\text{sd}} = \Delta x_{\text{nsd}} \|\nabla f(x)\|_\infty = - \frac{\partial f(x)}{\partial x_i} e_i$ （座標下降法）。
二階模型與信任區域
牛頓法使用二階泰勒近似： $$\hat{f}(x+v) = f(x) + \nabla f(x)^T v + \frac{1}{2} v^T \nabla^2 f(x) v$$ 此二次函數在 $v = \Delta x_{nt}$（牛頓步）時達到最小。我們定義一個 信任區域：集合 $\{v \mid \|v\|_2 \le \gamma\}$。參數 $\gamma$ 反映我們對二階模型的信心。當模型準確時，我們透過 $v = L^{-T}w = -L^{-T}L^{-1}P^T g$ 於KKT系統中求解。
🎯 收斂性的核心原則
效率由誤差 $f(x^{(k)}) - p^*$ 衰減的速度衡量。對於強凸函數， 誤差 $f(x^{(k)}) - p^*$ 收斂至零的速度至少與幾何級數一樣快。在迭代數值方法中，這稱為線性收斂。
- 次優性界： $p^* \geq f(x) + \lambda(x) + \log(1 - \lambda(x))$，僅當 $\lambda(x) < 1$ 時成立。
- 自協調性之和： 若 $f_1, f_2$ 為自協調函數，則 $f_1 + f_2$ 亦為自協調函數。
- 海森矩陣稀疏性： 若 海森矩陣帶狀結構條件：$\nabla^2 f(x)_{ij} = 0$ 對所有 $|i-j| > k$ 成立，則可提升效率。